package com.hutu;

import java.util.Arrays;
/**
 * 322. 零钱兑换
 * https://leetcode-cn.com/problems/coin-change/
 *
 * @author hutu
 * @date 2020/10/14 1:38 下午
 */
public class CoinChange {

    public static int coinChange(int[] coins, int amount) {
        // 特殊情况
        if(coins ==null||coins.length==0){
            return -1;
        }
        if(amount==0){
            return 0;
        }
        int length = coins.length;
        int[] dp = new int[amount+1];
        // 初始化
        Arrays.fill(dp,1,dp.length,Integer.MAX_VALUE);
        for(int i =0;i<length;i++){
            for(int j = coins[i];j<=amount;j++){
                // 还是初始值就是无解，跳过
                if (dp[j-coins[i]]!=Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{2}, 3));

    }
}
